package tree.leetcode_230_medium;

public class KthSmallest {
    public int kthSmallest(TreeNode root, int k) {
        while(root != null){
            TreeNode mostRight = root.left;
            if(mostRight != null){
                while(mostRight.right != null && mostRight.right != root){
                    mostRight = mostRight.right;
                }
                if(mostRight.right == null){
                    mostRight.right = root;
                    root = root.left;
                }else{
                    k--;
                    if(k == 0){
                        return root.val;
                    }
                    mostRight.right = null;
                    root = root.right;
                }
            }else{
                k--;
                if(k == 0){
                    return root.val;
                }
                root = root.right;
            }
        }
        return 0;
    }
}
